package com.hardy.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Author: Hardy
 * Date:   2021/1/8
 * Description:
 **/
public class Que51 {
    public static void main(String[] args) {

        System.out.println(new Solution().solveNQueens(4));
    }

    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            int[][] dp = new int[n][n];

            List<List<String>> res = new ArrayList<>();
            // (col, row)
            Map<Integer, Integer> col = new HashMap<>();
            // (row-col, row) (row+col, row)
            Map<Integer, Integer> dip1 = new HashMap<>();
            Map<Integer, Integer> dip2 = new HashMap<>();

            dfs(dp, n, 0, col, dip1, dip2, res);

            return res;
        }

        private void dfs(int[][] dp, int n, int i, Map<Integer, Integer> col,
                         Map<Integer, Integer> dip1, Map<Integer, Integer> dip2, List<List<String>> res) {
            if (i >= n) {
                List<String> r = new ArrayList<>();
                for (int x = 0; x < n; x++) {
                    StringBuilder str = new StringBuilder();
                    for (int y = 0; y < n; y++) {
                        str.append(dp[x][y] == 0 ? "." : "Q");
                    }
                    r.add(str.toString());
                }
                res.add(r);
            }

            // 遍历 行
            for (int j = 0; j < n; j++) {
                // 检查 列、斜
                if (col.containsKey(j)) continue;
                if (dip1.containsKey(j - i)) continue;
                if (dip2.containsKey(j + i)) continue;

                // 放入皇后
                dp[i][j] = 1;
                // cache
                col.put(j, i);
                dip1.put(j - i, i);
                dip2.put(j + i, i);

                // 递归
                dfs(dp, n, i + 1, col, dip1, dip2, res);

                // 退回
                dp[i][j] = 0;
                // cache
                col.remove(j);
                dip1.remove(j - i);
                dip2.remove(j + i);
            }
        }
    }
}
